#include <bits/stdc++.h>
using namespace std;

/*
3025. 人员站位的方案数 I
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个  n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [xi, yi] 。

 

计算点对 (A, B) 的数量，其中

A 在 B 的左上角，并且
它们形成的长方形中（或直线上）没有其它点（包括边界）。
返回数量。

 

示例 1：

输入：points = [[1,1],[2,2],[3,3]]

输出：0

解释：



没有办法选择 A 和 B，使得 A 在 B 的左上角。

示例 2：

输入：points = [[6,2],[4,4],[2,6]]

输出：2

解释：



左边的是点对 (points[1], points[0])，其中 points[1] 在 points[0] 的左上角，并且形成的长方形内部是空的。
中间的是点对 (points[2], points[1])，和左边的一样是合法的点对。
右边的是点对 (points[2], points[0])，其中 points[2] 在 points[0] 的左上角，但 points[1] 在长方形内部，所以不是一个合法的点对。
示例 3：

输入：points = [[3,1],[1,3],[1,1]]

输出：2

解释：



左边的是点对 (points[2], points[0])，其中 points[2] 在 points[0] 的左上角并且在它们形成的直线上没有其它点。注意两个点形成一条线的情况是合法的。
中间的是点对 (points[1], points[2])，和左边一样也是合法的点对。
右边的是点对 (points[1], points[0])，它不是合法的点对，因为 points[2] 在长方形的边上。
 

提示：

2 <= n <= 50
points[i].length == 2
0 <= points[i][0], points[i][1] <= 50
points[i] 点对两两不同。
*/

// 法一
class Solution {
public:
    int numberOfPairs(vector<vector<int>>& points) {
        int n = points.size();  // 点的总数
        int count = 0;          // 有效点对的数量

        // 遍历所有可能作为点A的点
        for (int i = 0; i < n; i++) {
            int x1 = points[i][0], y1 = points[i][1];   // A 点
            for (int j = 0; j < n; j++) {
                if (i == j)     continue;       // 不能同一个点
                int x2 = points[j][0], y2 = points[j][1];   // B 点

                // 看一下A是否在B的左上角 坐标大小相比来确定
                if (x1  > x2 || y1 < y2)    continue;
                // region有没有其他点
                bool valid = true;  // 当前点对是否有效

                // 检查其他点是否在A和B的矩形内
                for (int k = 0; k < n; k++) {
                    // 跳过AB
                    if (k == i || k == j)   continue;
                    int x = points[k][0], y = points[k][1];  // 其他点的坐标
                    // 检查点k是否在矩形区域内（包括边界）
                    // 矩形区域定义：x在[x1, x2]之间，y在[y2, y1]之间
                    if (x >= x1 && x <= x2 && y >= y2 && y <= y1) {
                        valid = false;  // 发现其他点，当前点对无效
                        break;          // 无需继续检查其他点
                    }
                }
                // 没有其他点在 cnt++
                if (valid)  count++;
            }
        }
        return count;
    }
};

// 法二
class Solution {
public:
    int numberOfPairs(vector<vector<int>>& points) {
        int ans = 0;
        // sort 按x坐标降序排列，若x相同则按y坐标升序排列
        // 确保后续遍历中，j > i时，points[j][0] <= points[i][0]（满足A在B左上角的x条件） 
        sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
            if (a[0] == b[0])   return a[1] < b[1];     // x相同时，y小的在后（避免同x时重复计算无效对）
            return a[0] > b[0];     // x不同时，x大的在前
        });

        // 固定B点
        for (int i = 0; i < points.size(); i++) {
            int up = INT_MAX;   // 记录当前找到的、符合条件的A点中最大的y值（初始设为极大值）   确保后续A点与B点形成的矩形内没有其他点

            // 寻找B点（i）对应的A点（j），j > i保证x[j] <= x[i]
            for (int j = i + 1; j < points.size(); j++) {
                // 左上角 坐标大小比对
                if (points[j][1] >= points[i][1] && points[j][1] < up) {
                    ans++;
                    // 更新up  后续有效才能继续更新
                    up = points[j][1];
                }
            }
        }
        return ans;
    }
};

// ranges 优化
class Solution {
public:
    int numberOfPairs(vector<vector<int>>& points) {
        // 排序策略：按x坐标升序排列，若x相同则按y坐标降序排列
        // 作用：确保后续j > i时，points[j][0] >= points[i][0]（满足A在B左上角的x条件）
        //      x相同时y降序，避免同x点之间重复计算无效对（因为同x时只有y大的能作为A）
        ranges::sort(points, {}, [](auto& p) { return pair(p[0], -p[1]); });
        
        int ans = 0, n = points.size();
        
        // 外层循环：固定A点（i为A的索引）
        for (int i = 0; i < n; i++) {
            int y1 = points[i][1];  // A点的y坐标
            int max_y = INT_MIN;    // 记录已找到的有效B点中最大的y坐标（初始为最小值）
            
            // 内层循环：寻找A点对应的B点（j为B的索引）
            // j > i：利用排序保证points[j][0] >= points[i][0]（x条件满足）
            // max_y < y1：当已找到的最大y超过A的y时，后续B点不可能满足条件，提前终止
            for (int j = i + 1; j < n && max_y < y1; j++) {
                int y2 = points[j][1];  // B点的y坐标
                
                // 条件1：y2 <= y1（满足A在B左上角的y条件）
                // 条件2：y2 > max_y（确保A和B形成的矩形内无其他点，因为max_y是已找到的最大y2）
                if (y2 <= y1 && y2 > max_y) {
                    max_y = y2;  // 更新最大y2，后续B点必须更大才可能有效
                    ans++;       // 找到有效点对(A,B)
                }
            }
        }
        return ans;
    }
};